Heap = {}
local P = Heap

function P.New(compFun)
	local newHeap = {}
	newHeap.list = {}
	newHeap.listCount = 0
	newHeap.compFun = compFun

	setmetatable(newHeap, {__index = P})

	return newHeap
end


function P:Add(t)
	if self.listCount < #self.list then
		self.list[self.listCount + 1] = t
	else
		self.list[#self.list + 1] = t
	end

	self.listCount = self.listCount + 1

	self:ShiftUp(self.listCount - 1)
end


function P:Count()
	return self.listCount
end


function P:Top()
	if self.listCount > 0 then
		return self.list[1]
	end

	return nil
end


function P:Pop()
    if self.listCount > 0 then
        local t = self.list[1];
        self.list[1] = self.list[self.listCount];
        self.listCount = self.listCount - 1

        self:ShiftDown(0)
        return t;
    end

    return nil
end

function P:ShiftUp(childIndex)
    if childIndex == 0 then
        return
    end

    local parentIndex = math.floor((childIndex - 1) / 2)
    if not self.compFun(self.list[parentIndex + 1], self.list[childIndex + 1]) then
        local t = self.list[parentIndex + 1]
        self.list[parentIndex + 1] = self.list[childIndex + 1]
        self.list[childIndex + 1] = t

        self:ShiftUp(parentIndex)
    end
end

function P:ShiftDown(parentIndex)
    local childIndex1 = parentIndex * 2 + 1;
    local childIndex2 = parentIndex * 2 + 2;

    local tempIndex = 0;
    if childIndex1 < self.listCount then
        if childIndex2 < self.listCount then
            if self.compFun(self.list[childIndex1 + 1], self.list[childIndex2 + 1]) then
                tempIndex = childIndex1
            else
                tempIndex = childIndex2
            end
        else
            tempIndex = childIndex1
        end
    elseif childIndex2 < self.listCount then
        tempIndex = childIndex2
    else
        return
    end

    if not self.compFun(self.list[parentIndex + 1], self.list[tempIndex + 1]) then
        local t = self.list[parentIndex + 1]
        self.list[parentIndex + 1] = self.list[tempIndex + 1]
        self.list[tempIndex + 1] = t

        self:ShiftDown(tempIndex)
    end
end

